#ifndef _BINARY_SEARCH_TREE_H_
#define _BINARY_SEARCH_TREE_H_

#include <stdlib.h>
#include <iostream>
#include <btree.h>

using namespace std;

template <class T> class BST;

template <class T>
class BstNode : public BTNode<T>
{
    friend class BST<T>;

protected:
    T data;
    BstNode<T> *left, *right, *parent;

public:
    BstNode() : left(NULL), right(NULL), parent(NULL) {}
    BstNode(const T d, BstNode<T> *L = NULL, BstNode<T> *R = NULL, BstNode<T> *P = NULL)
        : data(d), left(L), right(R), parent(P) {}
    ~BstNode() {}
    void set_data(T d) { data = d; }
    T get_data() { return data; }
    friend ostream & operator << (ostream &out, BstNode<T> & node)
    {
        out << "data: " << node.data;
        out << ", left: ";
        if (node.left)
           out << node.left->data;
        else
            out << "NULL";
        out << ", right: ";
        if (node.right)
           out << node.right->data;
        else
            out << "NULL";
        out << ", parent: ";
        if (node.parent)
            out << node.parent->data;
        else
            out << "NULL";
        out << endl;
        return out;
    }
};

template <class T>
class BST : public BTree<T>
{
private:
    BstNode<T> *root;
    T refValue;
    void make_empty(BstNode<T> *& ptr);
    void insert_i(T x, BstNode<T> *& root);
    void insert_r(T x, BstNode<T> *& root, BstNode<T> *parent);
    void remove_r(T x, BstNode<T> *& root);
    BstNode<T> * remove_i(T x, BstNode<T> *& root);
    void print_r(BstNode<T> *ptr) const;
    void print_i(BstNode<T> *ptr) const;
    BstNode<T> * search(T x, BstNode<T> *ptr) const;
    // iterative version
    BstNode<T> * search_i(T x, BstNode<T> *ptr) const;
    BstNode<T> * minimum(BstNode<T> *ptr) const;
    BstNode<T> * maximum(BstNode<T> *ptr) const;
    BstNode<T> * minimum_r(BstNode<T> *ptr) const;
    BstNode<T> * maximum_r(BstNode<T> *ptr) const;

public:
    BST() : root(NULL) {}
    BST(T v);
    ~BST() {}
    const BST & operator = (const BST & v);
    void make_empty() { make_empty(root); root = NULL; }
    //void insert(T v) { insert_i(v, root); }
    void insert(T v) { insert_r(v, root, root ? root->parent : NULL); }
    void remove(T v)
    {
        BstNode<T> * y = remove_i(v, root);
        if (y)
        {
            delete y;
        }
    }
    void print() const { print_i(root); }
    BstNode<T> * search(T x) { return search(x, root); }
    BstNode<T> * minimum() const { return minimum(root); }
    BstNode<T> * maximum() const { return maximum(root); }
    BstNode<T> * successor(BstNode<T> *ptr);
    BstNode<T> * predecessor(BstNode<T> *ptr);
    friend ostream& operator << (ostream&out, BST<T>& tree)
    {
        tree.print();
        return out;
    }
};

template <class T>
BstNode<T> *
BST<T>::search(T x, BstNode<T> *ptr) const
{
    if (ptr == NULL || ptr->data == x)
        return ptr;
    if (x < ptr->data)
        return search(x, ptr->left);
    else
        return search(x, ptr->right);
}

template <class T>
BstNode<T> *
BST<T>::search_i(T x, BstNode<T> *ptr) const
{
    while (ptr != NULL && ptr->data != x)
    {
        if (x < ptr->data)
            ptr = ptr->left;
        else
            ptr = ptr->right;
    }

    return ptr;
}

template <class T>
BstNode<T> *
BST<T>::minimum(BstNode<T> *ptr) const
{
    while (ptr && ptr->left)
        ptr = ptr->left;

    return ptr;
}

template <class T>
BstNode<T> *
BST<T>::minimum_r(BstNode<T> *ptr) const
{
    if (ptr && ptr->left)
        return minimum_r(ptr->left);

    return ptr;
}

template <class T>
BstNode<T> *
BST<T>::maximum(BstNode<T> *ptr) const
{
    while (ptr && ptr->right)
        ptr = ptr->right;

    return ptr;
}

template <class T>
BstNode<T> *
BST<T>::maximum_r(BstNode<T> *ptr) const
{
    if (ptr && ptr->right)
        return maximum_r(ptr->right);

    return ptr;
}

template <class T>
BstNode<T> *
BST<T>::successor(BstNode<T> *ptr)
{
    // with right child subtree?
    if (ptr && ptr->right)
        return minimum(ptr->right);

    // no right child subtree
    BstNode<T> *p = ptr ? ptr->parent : NULL;
    while (p && ptr == p->right)
    {
        ptr = p;
        p = ptr->parent;
    }

    return p;
}

template <class T>
BstNode<T> *
BST<T>::predecessor(BstNode<T> *ptr)
{
    if (ptr && ptr->left)
        return maximum(ptr->left);

    BstNode<T> *p = ptr ? ptr->parent : NULL;
    while (p && p->left == ptr)
    {
        ptr = p;
        p = ptr->parent;
    }

    return p;
}

template <class T>
void
BST<T>::insert_i(T v, BstNode<T> *& root)
{
    BstNode<T> *x = root, *y = NULL;

    while (x)
    {
        y = x;
        // already exist
        if (v == x->data)
        {
            cout << v << " already exist in tree!\n";
            return 0;
        }
        if (v < x->data)
            x = x->left;
        else
            x = x->right;
    }
    
    BstNode<T> *z = new BstNode<T>(v, NULL, NULL, y);

    // empty tree
    if (y == NULL)
        root = z;
    else
    {
        if (v < y->data)
            y->left = z;
        else
            y->right = z;
    }

    return 0;
}

template <class T>
void
BST<T>::insert_r(T v, BstNode<T> *& root, BstNode<T> *parent)
{
    if (root == NULL)
    {
        root = new BstNode<T>(v, NULL, NULL, parent); 
        return;
    }

    if (v == root->data)
    {
        cout << v << " already exist in tree!\n";
        return;
    }

    if (v < root->data)
        insert_r(v, root->left, root);
    else
        insert_r(v, root->right, root);
}

template <class T>
BstNode<T> *
BST<T>::remove_i(T v, BstNode<T> *& root)
{
    BstNode<T> *x = NULL, *y = NULL, *z = NULL;
    srand(time(NULL));

    if ((z = search(v)) == NULL)
    {
        cout << v << " not in tree!\n";
        return NULL;
    }

    // y is the node actually to splice out
    if (z->left == NULL || z->right == NULL)
        y = z;
    else
    {
        if (rand() % 2)
            y = successor(z);
        else
            y = predecessor(z);
    }
 
    // x take y's position. x may be NULL
    if (y->left)
        x = y->left;
    else
        x = y->right;

    cout << "z: " << *z;
    cout << "y: " << *y;
    cout << "x: ";
    if (x)
        cout << *x;
    else
        cout << "NULL\n";

    // y is spliced out
    // two boundary conditions:
    // first: modify x's parent
    if (x)
        x->parent = y->parent;
    // second: modify y's parent's child
    // root
    if (y->parent == NULL)
        root = x;
    else
    {
        if (y == y->parent->left)
            y->parent->left = x;
        else
            y->parent->right = x;
    }

    // cp data of spliced node y to z
    if (y != z)
    {
        z->data = y->data;
    }

    return y;
}

template <class T>
void
BST<T>::print_r(BstNode<T> *ptr) const
{
    if (ptr)
    {
        print_r(ptr->left);
        cout << *ptr;
        print_r(ptr->right);
    }
}

template <class T>
void
BST<T>::print_i(BstNode<T> *ptr) const
{
    if (ptr == NULL)
        return;

    BstNode<T> *p = ptr, *q = ptr, *pp = NULL;
    while(p->left)
        p = p->left;
    while (q->right)
        q = q->right;

    while (p != q)
    {
        cout << *p;

        // the same code as successor()
        if (p->right)
        {
            p = p->right;
            while (p->left)
                p = p->left;
        }
        else
        {
            pp = p->parent;
            while (p != q && p == pp->right)
            {
                p = pp;
                pp = p->parent;
            }
            p = pp;
        }
    }
    cout << *q;
}

#endif
